• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Electronic device for calculating trigonometric functions and uses thereof. This document details an electronic device that allows calculating a series of mathematical functions, more specifically a series of trigonometric functions by implementing a series of specialized circuits. The device object of the invention allows to calculate trigonometric functions of n {phi}, where n is a number that is supplied in base two as input and {phi} is a constant angle that can be chosen arbitrarily depending on the application. In particular, the trigonometric functions calculated by the device are sin (n {phi}) and com (n {phi}), the latter function being the complement of the cosine defined by com (x) = 1 - cos (x). (Machine-translation by Google Translate, not legally binding)
    公开号:ES2762745A1
    申请号:ES201831133
    申请日:2018-11-22
    公开日:2020-05-25
    发明作者:Martos David Guerrero；Calderón Alejandro Millán；Chico Jorge Juan；Cortés Julián Viejo；Díaz Manuel Jesús Bellido；De Clavijo Vázquez Paulino Ruiz；Arangüena Enrique Ostúa
    申请人:Universidad de Sevilla；
    IPC主号:
    专利说明:

    [0004] OBJECT OF THE INVENTION
    [0006] The present invention, as expressed in the statement of this specification, refers to a digital electronic method and device for calculating trigonometric functions and digital treatment of signals and images. More specifically, the object of the invention is a device, based on a digital electronic circuit, that allows calculating the sine and the cosine. Contrary to known developments, the object of the invention does not store cosine values in tables nor calculates them in an intermediate way. Instead it stores and / or calculates the complement of cosines, understanding as the complement of the cosine of an angle the result of subtracting the cosine of that angle from the unit. This novelty allows reducing the required resources and increasing the speed of operation.
    [0008] This invention has its application within the industry dedicated to the manufacture of electronic and / or computing devices that require the calculation of trigonometric functions, including in a non-exhaustive way those dedicated to the digital treatment of signals and images.
    [0010] BACKGROUND OF THE INVENTION
    [0012] Among the main objectives of designers of digital electronic circuits are reducing the area occupied by them, as well as reducing their energy consumption and increasing their speed. The reduction of area allows to reduce the production costs of the chips and generally leads to a reduction in consumption. The latter is especially important in portable equipment powered by batteries in order to increase their autonomy. In systems dedicated to the digital treatment of signals and images, the computation of trigonometric functions is essential. In particular, many of these systems integrate devices that calculate sines and / or cosines of multiples of an angle constant $, that is, they calculate sin (n $) and / or cos ( n $), where n is an integer that is provided as input to the device. Here are some of the applications of these devices:
    [0013] • Calculate the Fourier transform. The computation of this transform uses a series of complex coefficients called pivot factors ( twiddle factors) whose values are obtained from the corresponding sine / cosine pairs of certain multiples of the same angle $. For a transform of length L said angle is $ = - 2 n / L. Formally expressed, the pivot factors are the powers of the complex number e (-2 n / L) i. Thus, the pivot factor of index n will be (e (-2 n / L ^ n _ en ( - 2 n / L) i _ sin [n ( -2 n / L)] i cos [n ( _-2n / L)], that is, the sine / cosine pair of n <p where $ = - 2 n / L.
    [0014] • Implement digital systems whose function is to provide the sine and / or cosine of an angle expressed in a certain unit. To illustrate this, suppose one of these systems whose entry we will call I. It is evident that I has a finite number of bits, so the set of angles that it can represent is also finite. Let C be the set of absolute values of nonzero representable angles and let $ be the smallest element of C, all representable angles are positive or negative multiples of $, regardless of whether the input of the device is plotted at a fixed point, floating point or some integer notation. Therefore, the functionality of the system is equivalent to providing the sine and / or cosine with n being an integer.
    [0016] Henceforth we consider that the integer n is represented in unsigned base 2 notation. However, given the periodicity and symmetry properties of the sine and cosine functions, it is irrelevant if the notation used allows positive and negative values of n . To illustrate this with an example, let's look at the functionality of the circuit described by F. de Dinechin in his article “Fixed-Point Trigonometric Functions on FPGAs” in ACM SIGARCH Computer Architecture News Vol. 41, No. 5, December 2013. Said circuit calculates the sine and cosine of nx x is a number in the range [-1.1) represented in 2 's complement If I call the input circuit, w to the number of bits of I and S to the value represented by I in addition to 2 we have that x = S / 2W ~ 1 ^ nx = Sn / 2W ~ 1. Therefore, the circuit calculates the sine and the cosine of SQ being $ = n / 2w ~ 1. If n is the value represented by I in unsigned base 2 notation, it is easy to see that the sine / cosine of SQ coincides with that of n <p, so the functionality of this circuit is equivalent to calculating the sine and cosine of n <p. This is illustrated below for w = 3.
    [0019] Returning to the example of calculating the Fourier transform, since the calculation of trig functions is expensive in time, in hardware implementations of the transform where speed is critical, the pivot factors are pre-calculated in direct access memories (usually of type ROM). These memories can have a large number of positions because as many coefficients are required as samples have the series. This supposes a serious penalization in area and consumption in the computation hardware of long sequence transforms, being the size of the memories very large compared to the rest of the components, as pointed out by O. Gustafsson in his work “Analysis of Twiddle Factor Memory Complexity of Radix-2i Pipelined FFTs ”(Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers, 2009, pages 217-220). Therefore, several ways have been proposed to reduce the number of positions required when the length of the transform is power 2:
    [0020] • In 1976, D. Cohen showed that only a number of positions equal to half the number of samples was required in his article “Simplified control of FFT hardware” by IEEE Trans magazine. Acoust. Speech Signal Process (pages 577-579).
    [0021] • Between 1999 and 2000, Y. Ma, L. Wanhammar, Y. Chang, and KK Parhi reduced the number of positions to a quarter by storing only the angle coefficients in a range of one-quarter circumference. The rest is obtained easily and quickly by means of simple trigonometric relations that only require to swap and complement the stored values. See his article “Efficient FFT implementation using digit-serial arithmetic ”from the 1999 IEEE Workshop on Signal Processing Systems (pages 645-653) as well as“ Hardware efficient control of memory addressing for high performance FFT processors ”from IEEE Trans magazine. Signal Process (pages 917-921) from 2000.
    [0022] • In 2002 M. Hasan and T. Arslan reduced the number of positions to approximately one eighth of the number of samples by storing only the coefficients in an interval of one eighth in circumference. Again the remaining coefficients can be quickly calculated from them by applying trigonometric relationships. This is evident in his article “Scheme for reducing size of coefficient memory in FFT processor” in the February 14 issue of Electronics Letters magazine (pages 907-911).
    [0023] • In 2006 T. Sansaloni, A. Pérez-Pascual, V. Torres and J. Valls reduced the number of positions to exactly one eighth of the number of samples using specific hardware to detect and treat the coefficients whose real / imaginary part has a magnitude equal to 1 / V2. This allows to avoid the problems derived from implementing a semiconductor memory whose size is not a power of 2. His scheme is presented in his article “Scheme for Reducing the Storage Requirements of FFT Twiddle Factors on FPGAs” published in 2007 in the Journal of VLSI Signal Processing (pages 183-187).
    [0025] These optimizations are based on properties of symmetry and periodicity of the sine and cosine functions that are also used by F. de Dinechin to simplify his sine and cosine calculation circuit of nx in an optimization he calls argument reduction. Unfortunately, even applying all these improvements, the implementation of the transform still requires a memory of a number of positions that grows linearly with the number of samples. This is inconvenient in applications where the data sequence is long such as PLC or DVB-T2 (with lengths on the order of 213 and 215 respectively) or very long, as is the case with applications based on photon counting or the use of radio telescopes (with lengths on the order of 227 and 230 respectively). This was solved in patent P201600865 filed in October 2016. The patent requires memories whose total number of positions grows logarithmically with the number of samples instead of growing linearly. The patent used a device that calculates the complex in , that is, the sine and the cosine of n <p where n is a base 2-coded number that is supplied as input and $ a constant angle that can be chosen arbitrarily depending on the application. The device comprised the following components:
    [0026] • semiconductor memories (usually ROM type)
    [0027] • complex multipliers
    [0028] To describe the device of the patent P201600865, from now on we will use the following notation:
    [0029] w: number of input bits of the device
    [0030] I = IW- 1I W- 2 ... / i / 0: device input
    [0031] n = Xr = _o1 ^ t2t: value represented by the input
    [0032] m: number of memories used
    [0033] M0, M1, ^, M m_1: the m memories used
    [0034] Mk [d ]: content of the memory location Mk whose address is d
    [0035] L ( k): number of memory memory address lines Mk
    [0036] A ( _k) = A ( k) lk ^ -) _ 1 ... A ( k) 0: address lines of memory Mk
    [0037] nk = Y, LSo ~ 1A ( k) t2t: address represented by A (k)
    [0041] memories of index less than k
    [0042] <p k: angle defined by (2Si (A>) $
    [0044] The memories are chosen so that the total number of address lines matches the number of input bits of the device, so that
    [0045] m - 1
    [0046] w = SL ( m) = y L {k)
    [0048] The pre-calculated value that the memory locations contain is defined as follows:
    [0049] Mk [d] = ed $ kl = sin ( d ( pk) i cos ( d $ k)
    [0051] A direct access memory outputs the contents of the position whose address matches the number indicated by its address lines. Therefore, each memory Mk will output the sine and cosine of the angle nk <p k. On the other hand, the address lines of each Mk memory are connected to the input lines of the device that go from
    [0057] Due to this, the value n represented by the input can be written as follows:
    [0061] so that the multiple of the angle whose sine and cosine you want to calculate can be written like this:
    [0066] So the angle is the sum of the nkQk subangles . Since the sines and cosines of these subangles are found at the outputs of the memories, the sine and cosine of
    [0071] An alternative way of saying it is that the output of each Mk memory provides the complex
    [0072] It is equivalent to the calculation of the sine and the cosine of the sum of two angles from the sines and cosines of these angles and involves four simple products, one addition and one subtraction. Taking this into account, the graph of the device described in the patent has the form of a binary tree directed with m leaves in which each intermediate node has exactly two children. Each node corresponds to a component whose output is a unit module complex. The sheets correspond to the m memories and provide the enk ^ ki complexes. The rest of the nodes correspond to complex multipliers that calculate the product of the outputs of the components corresponding to their child nodes. The output of the device corresponds to that of the root node. Hereinafter we will call H at the height of said tree. Then it They comment on recommendations that, although not necessary for the device to work, improve the efficiency of the design:
    [0073] • To reduce the latency of the device, it is advisable to minimize the height of the 1H tree . This is accomplished using a full or semi-full binary tree. This type of tree is characterized in that the level of any pair of leaves differs by no more than unity.
    [0074] • The total number of memory locations is minimized when the number of address lines for each memory pair differs at most in the unit. To achieve this, let q be the quotient of dividing the number of input lines w by m and let r be the rest of said division, of the m memories, r should have q 1 address lines and the rest should have q lines of direction.
    [0075] • If the above recommendation is followed, the total number of memory locations decreases as the number of memories m increases . For a fixed tree height H , the maximum value of m is 2H, so the total number of memory locations is minimized for that value of m .
    [0077] An obvious application of this device is the calculation of the pivot factors of the Fourier transform. To do this, it would suffice to take $ = —2n / L, where L is the length of the transform. The number of bits of the input w would be the integer part by excess of log2 (i) so that w < 21og2 (L). If the default integer part of log2 (w) is taken as the height of the tree H, there would be no more than w memories of no more than two address lines each, so that the number of total memory locations will be limited by 22w < Qlog2 (L) . This dimension grows logarithmically with L. Although this alone saves a large amount of resources, if L is a power of 2, an even more optimized pivot factor calculation circuit can be used. The optimized circuit for L = 2 shown in figure 1. Your input has been named B = Bf _1Bf _2 ... B1B0 . It comprises the following components:
    [0078] • a device like the one described above to calculate the sine and the cosine of multiples of 2n / L (1)
    [0079] • five 2: 1 multiplexers (2)
    [0080] • an adder (3)
    [0081] • a set of logic gates (4)
    [0082] This circuit uses a scheme similar to that presented by T. Sansaloni so that the cases in which the multiple of - 2 n / L corresponds to the angles n ¡ 4, 3 ^ / 4, 5 ^ / 4 and 7 ^ / 4 they are detected with a simple logic gate (4a) and are treated separately. The gate simply checks whether the Bf _3 bit is worth 1 and the other least significant bits of B are worth 0, in which case the magnitude returned for the sine and cosine is 1 / V2 thanks to a pair of multiplexers (2b) . Unlike T. Sansaloni's scheme, this circuit does not use a ROM to obtain the sines and cosines of the multiples of $ = -2 n / L on the interval {-n / 4, 0]. Instead, a device like the one described above is used to calculate the sine / cosine pairs of the multiples of $ = 2n / L in the interval [0, n ¡ 4). This makes it possible to greatly reduce the memory required to implement the system. Furthermore, since the sines and cosines of all the angles in the interval [0, n ¡ 4) are positive, complex multipliers can be implemented using unsigned magnitude multipliers. When Bf _3 = 0 the input to the device that returns the sines and cosines is equal to the substring Bf _ABf _s ... B0. Otherwise the complement to two of said substring is made following the scheme of M. Hasan. For this, the multiplexer (2a) and the adder (3) are used. In the last stage a logic gate (4b) calculates the exclusive or operation of Bf _3 and Bf _2. If the result is 0, a pair of multiplexers (2c) will make the magnitude of the imaginary part and the real part equal to those of the sine and cosine calculated by the device respectively. Otherwise the imaginary and real magnitudes will be those of the cosine and the sine respectively. The sign of the real and imaginary part is calculated with simple logic gates (4c) as a function of Bf _2 and Bf _t.
    [0084] In the device described in patent P201600865, the lowest index memories encode the sine / cosine pairs at very small angles. This implies that your breasts will be very close to zero and your cosines very close to one, which allows you to carry out certain optimizations. To illustrate this, let's see how the patent P201600865 could be applied in the calculation of the pivot factors of a transform of length L = 211. In this example, the sine and cosine components of each coefficient are provided in fixed point notation with 8 bits of part fractional with no bit for the integer part, so the value one is approximated by 1 - 2_8. The optimized circuit of figure 1 will be used, which will include a device with 11 - 3 = 8 input lines to calculate the sine / cosine pairs of the multiples of $ = 27T / 211 = n / 210 in the interval [0, n ¡ 4). If the device is structured as a unit height tree, it will have the appearance shown in figure 2. Note that, to compensate for errors in rounding, the memories (5) must store the values with a precision of 17 bits. Memory M0 will encode the sines and cosines of the multiples of $ 0 = 20 $ = n / 2w, while memory M1 will encode the sines and cosines of the multiples of 0! = $ 24 = n / 26. The angles corresponding to memory M0 are much smaller than those corresponding to memory M 1, and are in the interval [0, 15rc / 210]. Since in [0, n 4) the sine is increasing, the largest sine encoded in M0 is that of ! Sn / 210, the representation of that sine has the four most significant bits at zero. This implies that all the sinuses of the M0 memory have these bits to zero, so it is not necessary to store them. On the other hand, since the cosine is decreasing in [0, n 4), the smallest cosine encoded in M0 is that of ! Sn / 210. The representation of this cosine has the nine most significant bits to one, which implies that all the cosines of the M0 memory have these bits to one and it is not necessary to store them. The same observations could be made with the M1 memory, but since the angles corresponding to it are larger, in M1 it is only possible to save one bit per pivot. This bit is the most significant of the cosines since it is worth 1 in all the cosines encoded in M 1. Note that the common zeros in the most significant bits of the sines allow reducing the size of the arithmetic circuitry. In this specific case, instead of four 17 x 17 bit multipliers, two 17 x 17 (6b) and two 13 x 17 (6a) were required. An important observation is that the common ones in the most significant bits of the cosines do not allow a similar optimization in the arithmetic circuitry. The following sections describe how the proposed invention overcomes this limitation.
    [0086] DESCRIPTION OF THE INVENTION
    [0088] The device object of the invention calculates trigonometric functions of n <p, where n is a number supplied in base two as input and $ is a constant angle that can be chosen arbitrarily depending on the application. In particular, the trigonometric functions calculated by the device are sin ( n $) and com ( n $), the latter function being the complement of the cosine defined by com ( x) = 1 - cos ( _x ). The device mainly comprises the following components:
    [0089] • Optionally, a set of registers that store the intermediate calculated values. These are only necessary if you want to perform a pipeline or sequential implementation.
    [0090] • Devices that we will call trigonometric adders and that we will represent with the letter T. The functionality of a trigonometric adder is to calculate the sine and the complement of the cosine of the sum of two angles from the sine and the complement of the cosine of these angles. To implement it, starting from the following trigonometric formulas
    [0091] sin ( AB) = sin ( A) cos ( B) cos ( A) sin ( B)
    [0092] cos {AB) = cos ( A) cos ( B) - sin ( A) sin ( B)
    [0093] we get the following
    [0094] sin ( AB) = sin ( A) sin ( B ) - [ sen ( A) com ( B ) com ( A) sin ( B )] com {AB) = com ( A) com ( B ) [sin ( _A) sin ( B) - com {A) com ( B )] Therefore, a trigonometric adder can be constructed from multipliers (6), adders (3) and subtractors (7) as shown in figure 3. Although It is not shown in this figure, as mentioned, between the different arithmetic circuits, registers can be placed if a pipeline or sequential implementation is desired.
    [0095] • A set of m devices with the functionality of lookup tables that we will call trigonometric tables and that we will represent by M0, Mt, ..., Mm_1.
    [0097] To describe the structure of the device in a similar way to that used in the background section with patent P201600865, we will use the following notation below:
    [0098] 0: chosen constant angle
    [0099] w: number of input bits of the device
    [0100] I = Iw- 1I w- 2 ... ltl 0: device input
    [0101] n = Xt '= _ o1 ^ t2t: value represented by the entry in base 2
    [0102] m: number of trigonometric tables used
    [0103] M0, M1, ..., Mm_1: the m trigonometric tables used
    [0104] L ( k): number of input lines of the trigonometric table Mk
    [0105] A ( _k) = 4 (k) ¿(k) _! ... A ( k) 0: input lines of the trig table Mk
    [0106] nk ( k) t2t: value represented by input A {k ) in base 2
    [0108] trigonometric tables of index less than k
    [0109] • angle defined by (2Si (k)) 0
    [0111] The functionality of each trigonometric table Mk is to provide the sine and the complement of the cosine of nk <p k. In a non-exhaustive and non-exclusive way, some ways of implementing them are proposed:
    [0112] • Mk can be a read-only direct access memory in which the content of each memory location of address d is the sine and complement of the cosine of d <pk.
    [0113] • Mk can be a read / write shortcut memory that is initialized before the device is put into operation so that each address memory location d is written with the sine and the complement of the cosine of d <p k .
    [0114] • Mk can be a circuit that provides the sine and the complement of the cosine of nk <pk by performing some type of calculation, such as the computation of an interpolation polynomial.
    [0115] • Mk can be a combination of memory and computational circuits that provide the sine and the complement of the cosine of nk <p k. For example, you can include a circuit that computes an interpolation polynomial connected to a memory that gives you the coefficients of that polynomial depending on the interval in which the input is.
    [0117] Trigonometric tables are chosen so that their total number of input lines equals the number of input lines on the device, so that
    [0121] The input lines of each trigonometric table Mk are connected to the input lines of the device that go from ISL ^ to ISL ( k + i) - i, that is, each line A ( _k) t is connected to the line h + sL ( k) so that
    [0124] A ( m 1) ¡w - l ■■■ h> L ( m - l) lh> L ( m - l)
    [0125] Due to this, the value n represented by input I can be written as follows:
    [0129] so that the multiple of the angle whose sine and complement of the cosine we want to calculate can be written like this:
    [0133] So the angle is the sum of the nkQ k subangles . Since the sines and complements of the cosines of these subangles are found at the outputs of the trigonometric tables, the sine and the complement of the cosine of n <p can be obtained from them using trigonometric adders. With this in mind, the device graph is shaped like a directed binary tree with m leaves in which each intermediate node has exactly two children. Each node corresponds to a component that provides at its output the sine and the complement of the cosine of an angle. The leaves correspond to the m trigonometric tables and provide the sines and cosine complements of the angles n0 $ 0, n1 ^ 1 ...... The rest of the nodes correspond to trigonometric adders that
    [0134] they receive the outputs of their child nodes as input. The output of the device corresponds to that of the root node. The connection between the inputs of a trigonometric adder and the outputs corresponding to its child nodes can be direct or, if a pipeline implementation is desired, through intermediate registers. If registers are used to store the intermediate values, a sequential implementation can be performed in which the number of trigonometric adders is less than the number of intermediate nodes in the circuit graph, reusing at least one of these trigonometric adders to compute two or more intermediate nodes. Hereinafter we will call H at the height of the tree. Recommendations are discussed below which, while not necessary for the device to function, improve design efficiency:
    [0135] • To reduce the latency of the device, it is convenient to minimize the height of the H- tree . This is achieved using a full or semi-full binary tree. This type of tree is characterized in that the level of any pair of leaves differs by no more than unity.
    [0136] • If direct access memories are used to implement trig tables, the total number of memory locations is minimized if the number of address lines in each memory pair differs by the unit at most. To achieve this, let w be the total number of address lines, m the number of memories, q the quotient of dividing w by m and let r be the rest of said division, of the m memories, r must have q 1 lines of address and the others must have q address lines.
    [0137] • If the previous recommendation is followed, the total size of the memories used to implement the trig tables decreases as their number increases. For a tree of height H the maximum number of trig tables is m = 2H.
    [0139] An obvious utility of this device is the calculation of the sine and the cosine of n <p, so it covers all the applications of the patent P201600865. As an example, Figure 4 shows how to use the device to calculate the sine and cosine of n <p using 11 bits to encode n (i.e. w = 11). The device has a binary tree structure of height 2 (H = 2). The number of trig tables has been maximized by making m = 2H = 4. The four trig tables, named M0, Mt, M2 and M3 have been implemented using ROM memories (8). Following the recommendation to minimize the total number of memory locations, M3 has been provided with two address lines (q = [w / m = 2) and the remaining three memories (r = w - mq = 3) have one more address line each, so that L (3) = 2 and L (2) = L (l) = ¿(0) = 3. Therefore SL (0) = 0, 0 O = 2>, SL (1) = 3, $ t = 230, SL (2) = 6, 02 = 260, SL ( _ 3) = 9 and 03 = 290. Each input line t of each trigonometric table Mk is connected to the line It + sL ( k), so the inputs of M0, M t, M2 and M3 are connected respectively to I2I1I0, / 5/4/3 , hhh e 710 / g. Each Mk contains the sines and the complements of the cosines of the multiples of 0k, so the sine and the complement of the cosine of nk <pk appear at its output. The device contains three trigonometric adders (9).
    [0141] The two directly connected to the trig tables calculate the sine and the complement of the cosine of the angle no0 or + n1 $ 1 and the angle n202 n 303 respectively. The one corresponding to the root calculates the sine and the complement of the cosine of n0 = no0 or n1 ^ 1 n2 <p2 n3 <p3. A trivial circuit (10) is connected to the output of the device that subtracts the complement of the cosine of n0 from the unit to obtain the cosine of n0.
    [0142] As in patent P201600865, if in a particular application the multiple of the angle is always between 0 and n¡2 radians then signed arithmetic circuits are not required. Furthermore, the proposed device has the advantage over said patent that the multipliers used do not receive cosines of angles as input, but rather the complement thereof. This allows to reduce the size of the multipliers. To illustrate this, let us return to the application example of patent P201600865 presented in the background section of the invention. In the example, to calculate the pivot factors of a transform of length 211, a device with a tree structure of height H = 1 was used that provided the sine / cosine pairs of the multiples of $ = 27T / 211 = n / 210 in the interval [0, n ¡ 4). The four most significant bits of the representation of the sinuses encoded in the M0 memory were equal to zero, which allowed reducing the size of two of the multipliers to 13 x 17, but the common ones in the representation of the cosines did not allow a similar optimization so that the other two multipliers had to remain 17 x 17. On the other hand, if the invention proposed now were used, the memories would not encode the cosines but the complement of them. As we saw, the angles corresponding to the memory M0 are in the interval [0, 15n: / 210]. As the complement of the increasing cosine in [0, n ¡ 4), the largest of those encoded in M0 would be that of 15rc / 210. Since the representation of this value has the 9 most significant bits at zero, all the cosine complements encoded in M0 would have said bits at zero. The same would happen with the most significant bit of the representation of the complement of the cosines of the memory M 1. Therefore, with the proposed invention, only a multiplier of 13 x 17 would be necessary, one of 13 x 16, one of 8 xl 7 and another 8 x 16. If you want to implement the transformation of a longer sample, the improvement will be even greater since the angles corresponding to the memories with the lowest index will be even smaller.
    [0144] DESCRIPTION OF THE DRAWINGS
    [0146] To complement the description that is being made and in order to help a better understanding of the characteristics of the invention, according to a preferred example of practical embodiment thereof, a set of drawings is included as an integral part of said description. where, illustrative and not limiting, the following has been represented:
    [0147] Figure 1.- Shows a diagram showing a circuit that calculates the pivot factors of the Fourier transform for samples of length L = 2¿ following the scheme of T. Sansaloni. The index of the coefficient to be calculated is encoded in the entry ... B0. The circuit comprises a device that calculates the sine and cosine of a multiple of $ = 2n / 2 f in the interval [0, n ¡ 4) (1). A multiplexer (2a) and an adder (3) are used so that the device that returns the sines and cosines receives as input Bf_ABf _s ... B0 when B ¡_3 = 0, or its complement to two when B ¡_3 = 1 A logic gate (4a) checks if the bit Bf _2 = 0 is worth 1 and the rest of the least significant bits of B are worth 0, in which case the magnitude returned for the sine and cosine is 1 / V2 thanks to a pair of multiplexers (2b). In the last stage, another logic gate (4b) calculates the exclusive or operation of B ¡_3 and Bf _2. If the output of said gate is 0, a pair of multiplexers (2c) will make the magnitude of the imaginary part and the real part equal to those of the sine and cosine calculated by subcircuit (1) respectively. Otherwise the imaginary and real magnitudes will be those of the cosine and the sine respectively. The sign of the real and imaginary part are easily calculated with simple logic gates (4c) as a function of Bf _2 and Bf_1.
    [0149] Figure 2.- Shows a diagram showing an example of use of the device of patent P201600865 that calculates the sines and cosines of the multiples of $ = 27T / 211 = n / 2w in the interval [0, n ¡4) . The input of the circuit is called I and has 11 - 3 = 8 bits. The circuit puts the sine and cosine of n <p at its output, where n is the number represented by I in base 2. In this example the outputs are provided in fixed point notation with 8 bits of fractional part without bit for the integer part , so the value 1 is approximated by 1 - 2 -8. The device in this example is structured as a unit height tree (H = 1) and comprises two small memories (m = 2H = 2), called M0 and M1 (5). Memory M0 encodes the sines and cosines of the multiples angles of $ 0 = 2 ° $ = n / 2w, while memory M1 encodes the sines and cosines of the multiples angles of 0! = $ 24 = n / 26 . Note that, to compensate for rounding errors, the memories must store the values with a precision of 17 bits. The angles corresponding to memory M0 are much smaller than those corresponding to memory M 1, and are in the interval [0,15n: / 210]. Since in [0, n ¡ 4) the sine is increasing, the largest sine encoded in M0 is that of 15n: / 210, and the representation of that sine has the four most significant bits to zero. This implies that all representations of the sinuses of the M0 memory have these bits set to zero, so there is no need to store those bits. On the other hand, since the cosine is decreasing in [0, n 4), the smallest cosine encoded in M0 is that of ! Sn / 210. The representation of this cosine has the nine most significant bits to one, which implies that all the representations of the cosines of the M0 memory have said bits to one and it is not necessary to store those bits. The same observations could be made with the M1 memory, but since the angles corresponding to it are larger, in M1 it is only possible to save one bit per pivot. This bit is the most significant of the cosines since it is worth 1 in all the cosines encoded in M1. The four least significant bits of I are connected to the M0 address lines and the remaining to the M1 address lines so that n = n0 n1 24 with n0 and n1 being the value represented by the M0 and M1 address lines respectively, therefore n <p = n0 $ n124 <p = n0 $ 0 n1 ^ 1. The sine and cosine of n <p are obtained from the outputs of the memories using four multipliers (6), an adder ( 3) and a subtractor (7). Since the sine and cosine of all angles in the interval [0, n ¡ 4) are positive, these arithmetic circuits use unsigned notation. The common zeros in the most significant bits of the sinuses allow to reduce the size of the arithmetic circuitry. In this specific case, instead of four 17 x 17 bit multipliers, two 17 x 17 (6b) and two 13 x 17 (6a) were required.
    [0151] Figure 3.- Shows a diagram showing a circuit, called a trigonometric adder, that calculates the sine and the complement of the cosine of the sum of two angles called A and B from the sines and the complement of the cosines of said angles. . The complement of the cosine of an angle is defined as the result of subtracting the cosine of that angle from unity. The circuit uses adders (3), subtractors (7) and multipliers (6) to obtain the results applying the formulas
    [0152] sin (A B) = sin (A) sin (B) - [sen (A) com (B) com (A) sin (B)]
    [0153] com {A B) = com (A) com (B) [sin (_A) sin (B) - com {A) com (B)]
    [0154] In these formulas com denotes the complement function of the cosine, that is, com (i) = 1 -cos (x).
    [0156] Figure 4.- Shows a diagram showing an example of use of the proposed invention to calculate the sine and cosine of n <p, $ being a constant angle and n the value represented by the entry / in base 2. For this the invention calculates the sine and the complement of the cosine of n <p, understanding the complement of the cosine of an angle as the result of subtracting the unit of the cosine of said angle. In the figure com denotes the complement function of the cosine, that is, com (i) = 1 - cos (x). In the example in this figure, input I is 11 bits (w = 11) and the invention has a binary tree structure of height 2 ( H = 2). The number of trigonometric tables (m ) has been maximized by making m = 2H = 4 . The four trigonometric tables, named M0, M1, M2 and M3 have been implemented using ROM memories (8). Following the recommendation to minimize the total number of memory locations, M3 has been provided with two address lines (q = [w / m = 2) and the remaining three memories (r = w - mq = 3) have one more address line each, so that L (3) = 2 and L (2) = L (l) = L (0) = 3. Therefore SL (0) = 0, 0o = 2O0, SL ( 1) = 3, 0! = 230, SL ( 2) = 6, 02 = 260, SL (3) = 9 and 03 = 290. Each memory Mk contains the sines and the complements of the cosines of the multiples of 0k = (2Si (k)) 0 , so that the sine and the complement of the cosine of nk <p k appear in its output, with nk being the value of its direction lines. Each input line t of each trigonometric table Mk is connected to the line It + SL ( k), so that the inputs of M0, Mt, M2 and M3 are respectively connected to / 2/1/0, / 5 / 4/3, / 8/7 / 6e / 10 / g. Therefore n = n02SL ^ 0 ^ n12SL ^ 1 >> n22SL ^ 2 >> n32SL ( 3 ^ ^ n <p = n02SL ( ° ^ <p n1 2Si 1 ^^ 0 n22Si (2) 0 n32Si (3) 0 = no0 or n1 ^ 1 n2 <p2 n303. In this example three trigonometric adders are used (9) .The two directly connected to the trigonometric tables calculate the sine and the cosine complement of the angle no0o n1 ^ 1 and the angle n202 n303 respectively The one corresponding to the root calculates the sine and the complement of the cosine of n0 = no0 or n1 ^ 1 n2 <p2 n303 A trivial circuit (10) that subtracts the complement of the cosine from n0 to the unit to obtain the cosine of n0.
    [0158] PREFERRED EMBODIMENT OF THE INVENTION
    [0160] In a preferred embodiment of the object of the invention, a Virtex 7 model XC7VX485T-2FFG1761 from the manufacturer Xilinx was implemented on a FPGA ( Field Programmable Gate Array) , a circuit that calculates the pivot factors of the Fourier transform for samples of length L = 215 in fixed point notation of 16 bits for the fractional part and 0 bits for the part whole. The synthesis has been carried out using the Xilinx Vivado Design Suite tool. In this synthesis, the DSP units integrated in the FPGA were used to implement the multipliers. Following the scheme of T. Sansaloni, the circuit uses a device with an input of 15 - 3 = 12 bits that calculates the sine and cosine of the multiples of 0 = 2n / 2is in the interval [0, n ¡ 4). Said device has been implemented using the proposed invention to calculate the sine and the complement of the cosine of the multiples of 0 = 2n / 2is. This example of the invention comprises two trig tables that have been implemented using the LUTs of the FPGA. Each of them has 12/2 = 6 input bits. A trivial arithmetic circuit subtracts the complement of the cosine from the unit to obtain the cosine. The implementation required 7 units of DSP. In order to make a comparison with the state of the art, a circuit with identical functionality has been implemented but that, instead of using the proposed invention, uses the device described in the previously commented document P201600865 to calculate the sine and cosine of 0 = 2n / 2is in the interval [0, n ¡ 4). Using the same FPGA and the same synthesis tool as in the previous case, the design required 12 DSP units. Therefore, the proposed invention provides a saving of almost 42% in said resources.
    权利要求:
    Claims (8)
    [1]
    1. Digital electronic device for calculating trigonometric functions characterized by comprising:
    - a w-bit input I through which it receives a number n in unsigned base 2 notation.
    The lines of this entry are numbered starting with zero in the form I = Zw_1 / w_2 ... hk,
    - outputs that provide sine and the complement of cosine of n <p, $ being a constant angle and being the complement of cosine the function defined by com (x) = 1 - cos (x), where eos is the cosine function ,
    - arithmetic circuitry comprising one or more circuits configured to carry out the addition, subtraction and multiplication operations, and
    - m components numbered from 0 to m - 1 named M0, Mt, ..., Mm_1 with the functionality of lookup tables, where:
    • each of them comprises an entry whose lines are numbered ascending starting with 0,
    • let SL be the function over Zm defined by:

    [2]
    2. Device according to the preceding claim, characterized in that it includes registers where the results of intermediate values are written.
    [3]
    3. Device according to the preceding claim, characterized in that, during the computation of an output of the device, at least one arithmetic circuit is reused to calculate more than one value.
    [4]
    Device according to one of claims 1 to 3, characterized in that the range of values represented by the input and the constant angle $ are such that the product of the input value n times $ is always an angle between 0 and n¡2 radians.
    [5]
    5. Device according to any of claims 1 to 4, characterized in that the arithmetic circuitry it includes does not perform signed operations.
    [6]
    6. Use of the digital electronic device described in any of claims 1 to 5 to calculate the cosine of n <p from the complement of the cosine of n <p.
    [7]
    7. Use of the digital electronic device described in any of claims 1 to 5 to calculate the pivot factors of a Fourier transform of length L taking as a constant angle $ = -2n L radians or $ = 2n / L radians.
    [8]
    8. Use of the digital electronic device described in any of claims 1 to 5 to calculate trigonometric functions of an arbitrary angle.
    类似技术:
    公开号 | 公开日 | 专利标题
    Fu et al.2010|FPGA designs with optimized logarithmic arithmetic
    Zhong et al.2006|A power-scalable reconfigurable FFT/IFFT IC based on a multi-processor ring
    Nguyen et al.2018|A high-performance, resource-efficient, reconfigurable parallel-pipelined FFT processor for FPGA platforms
    KR20160130700A|2016-11-14|Appartus and method for performing division operation, and system-on-chip having the same
    Revanna et al.2013|A scalable FFT processor architecture for OFDM based communication systems
    ES2762745B2|2021-11-26|ELECTRONIC DEVICE CALCULATING TRIGONOMETRIC FUNCTIONS AND USES OF THE SAME
    ES2762747A1|2020-05-25|ELECTRONIC DEVICE CALCULATOR OF TRIGONOMETRIC FUNCTIONS |
    Wang et al.2016|A pipelined area-efficient and high-speed reconfigurable processor for floating-point FFT/IFFT and DCT/IDCT computations
    ES2663168B2|2018-08-16|Digital electronic circuit for the calculation of sines and cosines of multiples of an angle
    Joshi et al.2014|Distributed arithmetic based split-radix FFT
    Ismail et al.2013|Hybrid logarithmic number system arithmetic unit: A review
    Mishra et al.2013|Implementation of custom precision floating point arithmetic on fpgas
    Savadi et al.2016|A survey on design of digital signal processor
    Wang et al.2014|$| $-Friendly Points: A Table-Based Method to Evaluate Trigonometric Function
    Varghese et al.2016|FPGA implementation of area-efficient IEEE 754 complex divider
    Singh et al.2016|Design and synthesis of single precision floating point division based on newton-raphson algorithm on fpga
    Liebig et al.2014|Low-latency double-precision floating-point division for FPGAs
    Vasudevan et al.2014|Image processing using approximate datapath units
    Yan et al.2013|Improved Goldschmidt division method using mapping of divisors
    Gustafsson et al.2010|Arithmetic
    Kalra et al.2017|Vedic multiplication based efficient OFDM FFT processor
    Cho2014|A Variable Latency K'th Order Newton-Raphson's Floating Point Number Divider
    Zhang et al.2013|n-Tuples of positive integers with the same sum and the same product
    Maharatna et al.2008|Reduced Z-datapath CORDIC rotator
    Harika et al.2014|Analysis of different multiplication algorithms & FPGA implementation
    同族专利:
    公开号 | 公开日
    ES2762745B2|2021-11-26|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US20050273483A1|2004-06-04|2005-12-08|Telefonaktiebolaget Lm Ericsson |Complex logarithmic ALU|
    US20140337401A1|2011-12-31|2014-11-13|Institute Of Automation, Chinese Academy Of Sciences|Data access method and device for parallel fft computation|
    WO2018104566A1|2016-10-10|2018-06-14|Universidad De Sevilla|Digital electronic circuit for calculating sines and cosines of multiples of an angle|
    法律状态:
    2020-05-25| BA2A| Patent application published|Ref document number: 2762745 Country of ref document: ES Kind code of ref document: A1 Effective date: 20200525 |
    2021-11-26| FG2A| Definitive protection|Ref document number: 2762745 Country of ref document: ES Kind code of ref document: B2 Effective date: 20211126 |
    优先权:
    申请号 | 申请日 | 专利标题
    ES201831133A|ES2762745B2|2018-11-22|2018-11-22|ELECTRONIC DEVICE CALCULATING TRIGONOMETRIC FUNCTIONS AND USES OF THE SAME|ES201831133A| ES2762745B2|2018-11-22|2018-11-22|ELECTRONIC DEVICE CALCULATING TRIGONOMETRIC FUNCTIONS AND USES OF THE SAME|
    [返回顶部]